package com.lw.leetcode.test;

import java.util.Arrays;

/**
 * @Author liw
 * @Date 2021/4/15 14:14
 * @Version 1.0
 */
public class Permutation {

    public static void main(String[] args) {

        for (int i = 0; i < 24; i++) {
            String permutation = new Permutation().getPermutation(4, i + 1);


            System.out.println(permutation);
        }

    }
    // 1 1 2 6
    // 1 2 6 24

    // 2   1 1 2 0
    // 3   1 2 -1 -1

    public String getPermutation(int n, int k) {
        // 先把集中特殊的情况直接返回
        if (n == 1) {
            return "1";
        }
        if (n == 2) {
            if (k == 1) {
                return "12";
            }
            return "21";
        }
        StringBuilder sb = new StringBuilder(n);
        if (k == 1) {
            for (int i = 0; i < n; i++) {
                sb.append(i + 1);
            }
            return sb.toString();
        }

        // 开始一般的形式

        int a = 1;
        int limit = 0;

        for (int i = 2; i <= n; i++) {
            a *= i;
            limit = i;
            if (a > k) {
                break;
            }
        }
        int[] arr = new int[n];
        Arrays.fill(arr, -1);
        int d = 0;
        for (int i = n - limit; i > 0; i--) {
            arr[d++] = 1;
        }
        a /= limit;

        int p;
        int z = d;
        while (k != 0) {
            p = k / a;
            k = k % a;
            if (k != 0) {
                p++;
            } else {
                if (z + 1 < n) {
                    arr[z + 1] = 0;
                }
            }
            a /= (--limit);
            if (z + 1 < n) {
                arr[z++] = p;
            }
        }
        int[] arr2 = new int[n];
        for (int i = 0; i < n; i++) {
            arr2[i] = i + 1;
        }

        for (int i = 0; i < n; i++) {
            int index = arr[i];
            if (index == 0) {
                for (int j = n - 1; j >= 0; j--) {
                    if (arr2[j] != 0 && arr2[j] != -1) {
                        sb.append(arr2[j]);
                    }
                }
                break;
            }
            if (index == -1) {
                for (int j = 0; j < n; j++) {
                    if (arr2[j] != 0 && arr2[j] != -1) {
                        sb.append(arr2[j]);
                    }
                }
                break;
            }
            int value = get(arr2, index, n);
            sb.append(value);
        }
        return sb.toString();
    }

    /**
     * 获取数组中的值
     * @param arr
     * @param index
     * @param n
     * @return
     */
    private static int get(int[] arr, int index, int n) {
        int num = 1;
        for (int j = 0; j < n; j++) {
            int i = arr[j];
            if (i != 0 && i != -1) {
                if (index == num) {
                    arr[j] = -1;
                    return i;
                }
                num++;
            } else if (i == 0) {
                return i;
            }
        }
        return -1;
    }

}
